//
// Created by grainlee on 16/9/22.
//

#include <iostream>
#include <vector>

#include "structure.h"
using namespace std;

ListNode* merge2lists(ListNode *l1, ListNode *l2){
    if(l1 == NULL && l2==NULL)
        return NULL;
    ListNode *tmp = new ListNode(0);
    tmp->next = l1;
    ListNode *cur = tmp;
    while (l1 != NULL && l2 != NULL){
        if(l1->val < l2->val){
            l1 = l1->next;
        }
        else{
            ListNode *next = l2->next;
            cur->next = l2;
            l2->next = l1;
            l2 = next;
        }
        cur = cur->next;
    }
    if (l2 != NULL)
        cur->next = l2;


    return tmp->next;
}

ListNode* merge(vector<ListNode*> &lists, int l, int r){
    if (l < r){
        int mid = (l+r)/2;
        return merge2lists(merge(lists,l,mid),merge(lists,mid+1,r));
    }
    return lists[l];
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.size() == 0)
        return NULL;
    return merge(lists,0,lists.size()-1);
}

int main(){
    vector<ListNode*> lists;
    ListNode *test = new ListNode(2);
    lists.push_back(test);
    ListNode *test1 = new ListNode(1);
    lists.push_back(test1);
    ListNode *res = mergeKLists(lists);
    while(res!=NULL){
        cout << res->val << " ";
        res = res->next;
    }

}